/**
 * Copyright (c) 2009-2011, chunquedong(YangJiandong)
 * 
 * This file is part of ChunMap project
 * Licensed under the GNU LESSER GENERAL PUBLIC LICENSE(Version >=3)
 * 
 * History:
 *     2010-05-05  Jed Young  Creation
 */
package chunmap.model.algorithm;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

import chunmap.model.coord.CoordSeqEditor;
import chunmap.model.coord.CoordinateSeq;
import chunmap.model.coord.Position;
import chunmap.model.elem.LineSegment;
import chunmap.model.elem.PointLineBag;

public class LineAlgorithm {
	static public boolean containLineString(CoordinateSeq points, CoordinateSeq other)
    {
        //打断
        CoordSeqEditor tLine = new CoordSeqEditor(other);
        tLine.tryInsertAll(points);
        // 片段在里面
        for (int i = 0, n = tLine.size() - 1; i < n; i++)
        {
            LineSegment lseg = tLine.getLineSegment(i);
            if (!containSegment(points, lseg))
            {
                return false;
            }
        }
        return true;
    }
    // 直接包含线段，不考虑线段跨结点情况
    static private boolean containSegment(CoordinateSeq points, LineSegment lseg)
    {
        for (int i = 0, n = points.size() - 1; i < n; i++)
        {
            LineSegment lseg2 = new LineSegment(points.getCoordinate(i), points.getCoordinate(i+1));
            if (lseg2.containLineSegment(lseg))
            {
                return true;
            }
        }
        return false;
    }

    static public boolean onLineString(CoordinateSeq points, Position p)
    {
        for (int i = 0, n = points.size() - 1; i < n; i++)
        {
            LineSegment lseg = new LineSegment(points.getCoordinate(i), points.getCoordinate(i+1));
            if (lseg.onLineSegment(p))
                return true;
        }
        return false;
    }

    //------------------------------------------------------------------------交集

    public static PointLineBag intersection(CoordinateSeq me, CoordinateSeq l2)
    {
        PointLineBag geometrys = new PointLineBag();
        List<MonotonyChain> chains1 = getMonotonyChains(me);
        List<MonotonyChain> chains2 = getMonotonyChains(l2);
        for (MonotonyChain chain1 : chains1)
        {
            for (MonotonyChain chain2 : chains2)
            {
                geometrys.add(chain1.intersection(chain2));
            }
        }
        return geometrys;
    }
    public static boolean hasIntersection(CoordinateSeq me, CoordinateSeq l2)
    {
        //PointLineBag geometrys = new PointLineBag();
        List<MonotonyChain> chains1 = getMonotonyChains(me);
        List<MonotonyChain> chains2 = getMonotonyChains(l2);
        for (MonotonyChain chain1 : chains1)
        {
            for (MonotonyChain chain2 : chains2)
            {
                if (chain1.hasIntersection(chain2))
                {
                    return true;
                }
            }
        }
        return false;
    }
    /**
     * 分解为单调链集合
     */
    public static List<MonotonyChain> getMonotonyChains(CoordinateSeq points)
    {
        List<MonotonyChain> chains = new ArrayList<MonotonyChain>();

        boolean forward = true;// 正向
        if (points.size() > 1)
        {
            if (points.startPoint().getX() > points.getCoordinate(1).getX())
            {
                forward = false;
            }
        }

        int n = points.size();
        int i = 0;

        while (i < n)
        {
            if (forward)
            {
                i = extractPositiveChain(points, chains, i);
                forward = false;
            }
            else
            {
                i = extractNegativeChain(points, chains, i);
                forward = true;
            }
        }
        return chains;
    }
    private static int extractPositiveChain(CoordinateSeq points
        , List<MonotonyChain> chains, int from)
    {
        MonotonyChain chain = new MonotonyChain();
        for (int i = from, n = points.size(); i < n; i++)
        {
            Position p = points.getCoordinate(i);
            if (!chain.add(p))
            {
                chains.add(chain);
                return i - 1;
            }
        }
        chains.add(chain);
        return points.size();
    }
    private static int extractNegativeChain(CoordinateSeq points
        , List<MonotonyChain> chains, int from)
    {
        MonotonyChain chain = new MonotonyChain();
        for (int i = from, n = points.size(); i < n; i++)
        {
            Position p = points.getCoordinate(i);
            if (!chain.insert(p))
            {
                chains.add(chain);
                return i - 1;
            }
        }
        chains.add(chain);
        return points.size();
    }

    //------------------------------------------------------------------------有效性检查

    public static boolean isSimple(CoordinateSeq points)
    {
        if (!checkOverPoint(points))
            return false;

        for (int i = 0, n = points.size() - 1; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                LineSegment ls1 = new LineSegment(points.getCoordinate(i), points.getCoordinate(i+1));
                LineSegment ls2 = new LineSegment(points.getCoordinate(j), points.getCoordinate(j+1));
                Object g = ls1.intersection(ls2);
                if (g == null)
                    continue;
                else if (g instanceof Position[])
                    return false;
                else if (g instanceof Position)
                {
                    Position p = (Position)g;
                    if (!isNodePoint(ls1, ls2, p))
                    {
                        return false;
                    }
                }
            }
        }
        return true;
    }
    private static boolean isNodePoint(LineSegment ls1, LineSegment ls2, Position p)
    {
        boolean isBorder1 = ls1.onBorder(p);
        boolean isBorder2 = ls2.onBorder(p);

        if (isBorder1 && isBorder2)
        {
            return true;
        }
        return false;
    }
    // 重叠点检测
    private static boolean checkOverPoint(CoordinateSeq points)
    {
        HashSet<Position> set = new HashSet<Position>();

        if (points.size() < 4)
        {
            return !hasOverPoint(points);
        }
        for (int i = 1, n = points.size() - 1; i < n; i++)
        {
            Position p = points.getCoordinate(i);
            if (set.contains(p))
            {
                return false;
            }
            else
            {
                set.add(p);
            }
        }
        if (existPointAt(points, 1))
        {
            if (points.startPoint().equals(points.getCoordinate(1)))
            {
                return false;
            }
        }
        if (existPointAt(points, points.size() - 2))
        {
            if (points.endPoint().equals(points.getCoordinate(points.size() - 2)))
            {
                return false;
            }
        }
        return true;
    }
    // 是否有重叠点
    private static boolean hasOverPoint(CoordinateSeq points)
    {
        HashSet<Position> set = new HashSet<Position>();
        for (Position p : points)
        {
            if (set.contains(p))
            {
                return true;
            }
            else
            {
                set.add(p);
            }
        }
        return false;
    }
    private static boolean existPointAt(CoordinateSeq points, int i)
    {
        if ((i < points.size()) && i >= 0)
            return true;
        return false;
    }
}